The matching of features in images representing a scene viewed from at least two different viewing positions is a major problem in stereo vision in the art of machine vision systems. To date, this problem has been approached by applying a set of constraints so that areas or features or both in two or more images are matched. This approach has met with varying degrees of success because there is no general solution to the problem and a set of constraints applied to one scene may not be appropriate to other scenes. Improperly applied constraints will lead to an interpretation of the images which does not correspond fully with the scene.
There is a reduction of one dimension when a three-dimensional (3D) scene is captured in a two-dimensional (2D) image. This dimensional reduction results in a loss of information about the scene because a point in the 2D image will correspond to a line in the 3D scene. Thus, the process of 2D image formation can be regarded as a many-to-one mapping. I.e., many points in the 3D space of the scene will map onto a single point in the 2D space of the image. Thus, the inverse operation of mapping 2D image space points onto 3D scene space points is a one-to-many mapping.
This loss of information can be and is avoided by using at least one further image of the scene taken from a different viewing position and then identifying corresponding points in the plural images that relate to the same point in the 3D space of the scene. In this way, the process of mapping 2D image space points on to 3D scene space points is reduced to a one-to-one mapping. However, in adopting this approach a new problem is created, namely, the problem of identifying corresponding points in the plural images, i.e., the correspondence problem. For any one pixel in one image, there will be a large number of possibly corresponding pixels in the or each other image, the extreme being every pixel in the other image being a possible match with the pixel in the first pixel, and there is of course only one correct corresponding pixel.